#pragma once

#include <vector>
#include <queue>
#include "containers/pqueue.h"

#define WTNA 0
#define WBWA 1

/** A block in the cache */
class Block 
{
  /** tag, idx, ofs bit length */
  int tagSize_, idxSize_, ofsSize_;
public:
  /** valid and dirty bits */
  bool valid, dirty;
  /** the tag and of this block, also the access time for LRU algorithm */
  unsigned int tag, idx, time;

  /** Constructor */
  Block(int tagSize, int idxSize, int ofsSize);

  /** Copy another block, take care of different tag & idx lengths*/
  void copy(const Block& b);

  /** Combination of tag and idx */
  unsigned int addr(void) const;

  /** Set all information of this block */
  void setAll(bool valid, bool dirty, unsigned int tag, unsigned int idx, unsigned int time);
};

/** Comparator of two blocks in a set
 *  Return true if lhs.time < rhs.time
 *  Use block index in the set rather than the block itself
 */
class Earlier
{
public:
  std::vector<Block>& b_;

  /** Constructor using blocks of a set */
  Earlier(std::vector<Block>& b) : b_(b) { assert(b_.size() > 0); }

  /** Compare function using block index */
  bool operator()(int i, int j) const { 
    assert((unsigned int)i < b_.size() && (unsigned int)j < b_.size() && i >= 0 && j >= 0); 
    return b_[i].time < b_[j].time;
  } 

  /** Debug print */
  void print() const {
    cout << "Earlier size = " << b_.size() << "\n";
    assert(b_.size() > 0);
  }
};

/** A set in the cache */
class Set
{
public:
  /** tag, idx, ofs bit length */
  int tagSize_, idxSize_, ofsSize_;

  /** The blocks of this set */
  std::vector<Block> blocks_;

  /** Block comparator */
  Earlier earlier_;

  /** Mapped priority queue for tags and block indices,
   *  used for searching tags and LRU blocks
   */
  pqueue<unsigned int, int, Earlier> tags_;

  /** Unused blocks */
  std::queue<int> unused_;

  /** Constructor */
  Set(unsigned int n_block, int tagSize, int idxSize, int ofsSize);

  /** Copy constructor */
  Set(const Set& s);

  /** Find a block using tag, return -1 if not found */
  int find(unsigned int tag);

  /** Find the least recently used block, return an invalid block if possible */
  int findLRU(void);

  /** Copy a block to a position in blocks */
  void setBlock(int block, const Block& b);

  /** Remove a block */
  void removeBlock(int block);

  /** Replace a block with a new block (with same tag) */
  void replaceBlock(int block, const Block& b);
};

/** The cache */
class Cache
{
public:
  /** Cache parameters */
  int C_, B_, S_, WP_, V_;
  bool verbose_;

  /** tag, idx, ofs bit length */
  int tagSize_, idxSize_, ofsSize_;

  /** number of sets, blocks per set, and bytes per block */
  unsigned int n_set_, n_block_, n_byte_;

  /** The sets of this cache */
  std::vector<Set> sets_;

  /** The victim cache, NULL if this is a victim cache */
  Cache* vc_;

  /** Statistics */
  int n_access_, n_time_;
  int n_read_, n_readmiss_, n_readmissall_;
  int n_write_, n_writemiss_, n_writemissall_;
  int n_mem_, n_writeback_;

  /** Current access information */
  unsigned int addr_, tag_, idx_, ofs_;
  int set_, block_;
  bool isRead_;
public:
  /** Constructor */
  Cache(int C, int B, int S, int WP, int V, bool verbose = true);

  /** Destructor */
  ~Cache(void);

  /** Process a memory access */
  void access(char rw, unsigned int addr);

  /** Split the address into tag, idx, ofs */
  void split(unsigned int addr);

  /** Check hit or not */
  bool isHit(void);

  /** process Hit, Victim Cache Hit, and Miss All */
  void doHit(void);
  void doMiss(void);
  void doVCHit(void);

  /** Return currently active block and current set */
  Block& currentBlock() { assert(set_ >= 0 && (unsigned int)set_ < n_set_ && block_ >= 0 && (unsigned int)block_ < n_block_); return sets_[set_].blocks_[block_]; }
  Set& currentSet() { assert(set_ >= 0 && (unsigned int)set_ < n_set_); return sets_[set_]; }

  /** Return cache size in bits */
  int size() const;

  /** Print cache content */
  void print_content(const char* name) const;
};
